package net.cloudsun.graph.core;

import java.util.*;

/**
 * 加权图
 *
 * @author Ryan
 * @since 1.0
 */
public class WeightedGraph<E> implements Graph<E>{
    /**
     * 节点
     */
    protected E[] vertices;
    /**
     * 边
     */
    protected List<? extends WeightedEdge>[] edges;

    public WeightedGraph(E[] vertices, List<? extends WeightedEdge>[] edges) {
        this.vertices = vertices;
        this.edges = edges;
    }

    public List<E> bfs(int first, int finalState) {
        // 宽度搜索。直接一个Deque
        HashMap<Integer,Integer> parentMap = new HashMap<>();
        HashSet<Integer> visited = new HashSet<>();

        Deque<Integer> deque = new LinkedList<>();
        deque.offer(first);

        Integer e = null;
        while (!Objects.equals(e, finalState) && !deque.isEmpty()) {
            e = deque.pollFirst();
            visited.add(e);
            List<? extends WeightedEdge> edgeList = this.edges[e];
            for (WeightedEdge edge : edgeList) {
                // 这里决定parent
                if (!visited.contains(edge.getTo())) {
                    parentMap.put(edge.getTo(), edge.getFrom());
                    deque.offerLast(edge.getTo());
                }
            }
        }
        List<E> path = new ArrayList<>();
        if (Objects.equals(e, finalState)) {
            for (Integer i = e; i != null; i = parentMap.get(i)) {
                E vertex = vertices[i];
                path.add(vertex);
            }
        }

        visited.clear();
        parentMap.clear();
        return path;
    }

    public Set<Integer> bfs(int first) {
        // 宽度搜索。直接一个Deque
        HashMap<Integer,Integer> parentMap = new HashMap<>();
        HashSet<Integer> visited = new HashSet<>();

        Deque<Integer> deque = new LinkedList<>();
        deque.offer(first);

        Integer e;
        while (!deque.isEmpty()) {
            e = deque.pollFirst();
            visited.add(e);
            List<? extends WeightedEdge> edgeList = this.edges[e];
            for (WeightedEdge edge : edgeList) {
                // 这里决定parent
                if (!visited.contains(edge.getTo())) {
                    parentMap.put(edge.getTo(), edge.getFrom());
                    deque.offerLast(edge.getTo());
                }
            }
        }

        return visited;
    }

    public E[] getVertices() {
        return vertices;
    }

    /**
     * 最短路径
     * @return 列表
     */
    public int[] shortestPath(int source) {
        // 首先一个set T
        final HashSet<Integer> t = new HashSet<>();
        // cost是一个数组啊
        int[] cost = new int[vertices.length];
        Arrays.fill(cost, Integer.MAX_VALUE);
        cost[source] = 0;
        int[] parent = new int[vertices.length];
        parent[source] = -1;
        while (t.size() < vertices.length) {
            // u 要是最短的 u not in t with the smallest cost
            int u = findU(t, cost);
            t.add(u);
            for(WeightedEdge edge : edges[u]) {
                final int v = edge.getTo();
                if (cost[v] > cost[u] + edge.getWeight()) {
                    cost[v] = cost[u] + edge.getWeight();
                    parent[v] = u;
                }
            }
        }
        return parent;
    }

    private int findU(HashSet<Integer> t, int[] cost) {
        final ArrayList<Integer> temp = new ArrayList<>();
        for (int i = 0; i < vertices.length; i++) {
            if (!t.contains(i)) {
                temp.add(i);
            }
        }
        int u = temp.get(0);
        // 找出最小的索引
        for (int i = 1; i < temp.size(); i++) {
            if (cost[temp.get(i)] < cost[u]) {
                u = temp.get(i);
            }
        }
        return u;
    }
}
